import java.util.PriorityQueue;

public class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int len = nums.length;

        PriorityQueue<Integer> heap = new PriorityQueue<>();

        for (int num : nums) {
            heap.offer(num);
        }

        //每次将最小的改变符号
        while (k > 0) {
            int num = heap.poll();
            heap.offer(num * (-1));
            k--;
        }

        int sum = 0;
        for (int num : heap) {
            sum += num;
        }
        return sum;
    }
}
